Video sharing websites such as YouTube.com™ facilitate user searches for video content and make a large number of videos viewable by the public. When a user performs a keyword search for video content, the user may be offered a series of thumbnail images representative of videos returned in the search. High-traffic video sharing websites maintain user-searchable indices and may add hundreds or even thousands of additional videos every day. Therefore, one challenge that website managers face is the need to quickly generate thumbnail images representative of each new video uploaded. Increased viewership of certain videos is desirable, in particular, by advertisers that display advertisements alongside videos or before, during, or after a video is played. Therefore, another challenge is ensuring that the thumbnails will be both visually stimulating and representative of the content in the underlying video so that the user will be encouraged to click on the thumbnail and view the associated video.